package com.explorati.LeetCode80.removeDuplicates;

/**
 * 80. Remove Duplicates from Sorted Array II
 * 
 * Given nums = [1,1,1,2,2,3], Your function should return length = 5, with the
 * first five elements of nums being 1, 1, 2, 2 and 3 respectively. It doesn't
 * matter what you leave beyond the returned length.
 * 
 * Given nums = [0,0,1,1,1,1,2,3,3], Your function should return length = 7,
 * with the first seven elements of nums being modified to 0, 0, 1, 1, 2, 3 and
 * 3 respectively.
 * 
 * @author explorati
 *
 */
public class Solution {

	public static int removeDuplicates(int[] nums) {
		// i记录最后一个符合要求的元素的位置
		int i = 0;
		// 利用j判断重复元素个数, j < 1为可重复边界，即不需移除
		int j = 0;
		for (int k = 1; k < nums.length; k++) {
			// 若位置为k的元素等于最后一个符合要求的元素的位置
			if (nums[k] == nums[i]) {
				if (j < 1) {
					// swap(nums, ++ i, k);
					// 这样亦可，即多判断一次 i 的下一个位置是否为相等元素，若是则省去移动
					if (++i != k) {
						swap(nums, i, k);
					}
					j++;
				}
			} else {
				// 位置为k的元素大于最后一个符合要求的元素的位置
				// 交换第一个不符合条件的值和位置为k的符合元素的值
				swap(nums, ++i, k);
				// 交换完之后,维护j
				j = 0;
			}
		}

		return i + 1;
	}

	public static void swap(int[] nums, int i, int j) {
		int temp = nums[i];
		nums[i] = nums[j];
		nums[j] = temp;
	}

	public static void main(String[] args) {
		int[] arr = { 1, 1, 1, 2, 2, 3 };
		removeDuplicates(arr);
		for (int i : arr) {
			System.out.print(i + "  ");
		}
	}
}
